package 前k个高频元素;

import java.util.*;

//给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
//
//
//
//示例 1:
//
//输入: nums = [1,1,1,2,2,3], k = 2
//输出: [1,2]
//示例 2:
//
//输入: nums = [1], k = 1
//输出: [1]
public class Solution {
    public static int[] topKFrequent(int[] nums, int k) {
        //先得出元素与出现频率的map
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }
        //解法1：桶排序
        //把频率一样的放到一个桶里面，然后按频率（桶）的大小，返回里面的元素
        //桶其实就是加一个维度汇总
        //索引为频率，所以+1，值是一个List，是相同频率的数字列表
        List<Integer>[] buckets = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry :
                freqMap.entrySet()) {
            int freq = entry.getValue();
            if (buckets[freq]==null)
                buckets[freq]=new ArrayList<Integer>();
            buckets[freq].add(entry.getKey());

        }
        ArrayList<Integer> res = new ArrayList<>();
        //从高频率向低频率收集，索引是频率，所以倒序遍历
        for (int i = buckets.length-1; i >=0&&res.size()<k; i--) {
            if (buckets[i]!=null)
                res.addAll(buckets[i]);
        }
        return res.stream().mapToInt(i->i).toArray();
    }

    public static int[] topKFrequent0(int[] nums, int k) {
        //先得出元素与出现频率的map
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }
        //解法2:简单的利用java api排序取频率最大
        //换一个容器，hashmap没有顺序
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(freqMap.entrySet());
        //Collections.sort默认是归并排序，升序排序，降序排序需要像下面那样，传结果是-1的
        list.sort((a, b) -> {
            return b.getValue() - a.getValue();
        });
        int[] res =new int[k];
        for (int i = 0; i < k; i++) {
            res[i]=list.get(i).getKey();
        }
        return res;
    }
    public static int[] topKFrequent1(int[] nums, int k) {
        //先得出元素与出现频率的map
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }
        //解法3:堆排序
        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] s={1,1,1,2,2,3};
        System.out.println(topKFrequent(s,2));
    }
}
